package PersonStu.sanqi;

/**
 * @Author: Dijah
 * @Date: 2022/10/25 11:35
 * @Desc:
 *
 * 有关二叉树的最大路径和的问题
 */
public class code_04_maxSumInTree {

    public static class Node{
        private int value;
        private Node node;
        private Node left;
        private Node right;

        public Node(){}

        public Node(int value){
            this.value = value;
            this.left = null;
            this.right = null;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node) {
            this.node = node;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }


    public static int maxSum = Integer.MIN_VALUE;

    /**
     * 从头结点出发，到叶节点返回最大路径和
     * @param node
     * @return
     * 之前的路径和pre
     */
    public static int maxPath(Node node){
        maxSum = Integer.MIN_VALUE;
        p(node,0);
        return maxSum;
    }

    public static void p(Node node,int pre){
        if(node.left == null && node.right == null){
            maxSum = Math.max(maxSum,pre + node.value);
        }
        if(node.left != null){
            p(node.left,pre + node.value);
        }
        if(node.right != null){
            p(node.right,pre + node.value);
        }
    }

    /**
     * 2、路径从任何节点出发，必须往下走，达到任何节点，返回最大路径和
     *
     * desc：
     * 1、和node无关的时候，
     *      a、左树上的整体最大路径和
     *      b、右树上的整体最大路径和
     * 2、和node有关的时候
     *      a、node自己
     *      b、node往左走
     *      c、node往右走
     * @param node
     * @return
     */
    public static int maxSum2(Node node){
        if(node == null){
            return 0;
        }
        return f2(node).allTreeMaxSum;
    }

    private static Info f2(Node node) {
        if(node == null){
            return null;
        }
        Info leftInfo = f2(node.left);
        Info rightInfo = f2(node.right);
        int p1 = Integer.MIN_VALUE;
        if(node.left != null){
            p1 = leftInfo.allTreeMaxSum;
        }
        int p2 = Integer.MIN_VALUE;
        if(node.right != null){
            p2 = rightInfo.allTreeMaxSum;
        }
        //开始和node有关
        int p3 = node.value;
        int p4 = Integer.MIN_VALUE;
        if(leftInfo != null){
            p4 = leftInfo.fromHeadMaxSum + node.value;
        }
        int p5 = Integer.MIN_VALUE;
        if(rightInfo != null){
            p5 = rightInfo.fromHeadMaxSum + node.value;
        }
        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
        int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return new Info(allTreeMaxSum,fromHeadMaxSum);
    }

    public static class Info{
        public int allTreeMaxSum;
        public int fromHeadMaxSum;
        public Info(int all, int from) {
            allTreeMaxSum = all;
            fromHeadMaxSum = from;
        }
    }


    /**
     * 从任何节点出发，到任何节点，最大路径和
     * @param node
     * @return
     *
     * 1、node无关的时候，
     *      a、左树上的最大路径和
     *      b、右树上的最大路径和
     * 2、node有关的时候
     *      a、node自己
     *      b、node往左走
     *      c、node往右走
     *      d、往左和往右
     */
    public static Info f3(Node node){
        if(node == null){
            return null;
        }
        Info leftInfo = f3(node.left);
        Info rightInfo = f3(node.right);
        int p1 = Integer.MIN_VALUE;
        if(leftInfo != null){
            p1 = leftInfo.allTreeMaxSum;
        }
        int p2 = Integer.MIN_VALUE;
        if(rightInfo != null){
            p2 = rightInfo.allTreeMaxSum;
        }
        //和node有关的时候
        int p3 = node.value;
        int p4 = Integer.MIN_VALUE;
        if(leftInfo != null){
            p4 = leftInfo.fromHeadMaxSum + node.value;
        }
        Integer p5 = Integer.MIN_VALUE;
        if (rightInfo != null){
            p5 = rightInfo.fromHeadMaxSum + node.value;
        }
        int p6 = Integer.MIN_VALUE;
        if(leftInfo != null && rightInfo != null){
            p6 = leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum + node.value;
        }

        int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(Math.max(p4, p5), p6));
        int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
        return new Info(allTreeMaxSum, fromHeadMaxSum);
    }

    /**
     * 从任何节点出发，必须到达叶节点的最大路径和
     * @param node
     * @return
     */
    public static int max = Integer.MIN_VALUE;



    public static int bigShuai(Node head) {
        if (head.left == null && head.right == null) {
            max = Math.max(max, head.value);
            return head.value;
        }
        int nextMax = 0;
        if (head.left != null) {
            nextMax = bigShuai(head.left);
        }
        if (head.right != null) {
            nextMax = Math.max(nextMax, bigShuai(head.right));
        }
        int ans = head.value + nextMax;
        max = Math.max(max, ans);
        return ans;
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(-5);
        Node node4 = new Node(5);
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        int i = bigShuai(node);
        System.out.println(i);

        int i1 = maxPath(node);
        System.out.println(i1);
    }

}
